
#include <iostream>
#include <vector>
#include <algorithm>


/*
 * 快速排序是一种典型的分治法，本质上是一种交换排序，是在冒泡排序的基础上改进而来；
 * 核心思想：通过一趟排序将要排序的数据分割成独立的两部分，
 *         其中一部分的所有数据比另一部分的所有数据要小，再按这种方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，使整个数据变成有序序列。
 * 实现过程：第一步单趟排序找到分治的中间位置，然后对左右两边递归继续进行排序
 *         
*/

using namespace std;

template<typename T>
void quickSort(typename std::vector<T>::iterator begin, typename std::vector<T>::iterator end)
{
    if (begin >= end)
    {
        return;
    }

    auto left = begin;
    auto right = end -1;
    auto keyi = begin;

    while (left < right)
    {
        while ((left < right) && (*right >= *keyi))
        {
            right--;
        }

        while ((left < right) && (*left <= *keyi))
        {
            left++;
        }

        swap(*right,*left);
        
    }

    swap(*right,*keyi);

    keyi = right;

    quickSort<int>(begin,keyi - 1);
    quickSort<int>(keyi + 1,end);
    
}

int main() {
    std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
    quickSort<int>(v.begin(), v.end());
    for (auto i : v) {
        std::cout << i << " ";
    }
    std::cout << std::endl;

    const int & p = 10;// 常量左值引用可以绑定到右值
    
    int a[3] {1,2,3};

    decltype(a) hu; // 自动判断类型

    auto ju = a[0];

    cout << sizeof(hu) << endl;

    cout << sizeof(ju) << endl;

    return 0;
}


